In a storage device including a magnetic disk, a controller of the storage device typically receives commands such as write commands and read commands from a host and executes the received commands, e.g., accesses the magnetic disk for writing data and reading data. Each command sent from the host typically includes a logical address (representing a logical location) or a physical location of the magnetic disk to designate a target position of the disk to be accessed. The controller causes a head to be positioned at the target position as the magnetic disk is rotating, such the head can write data to or read data from the target position of the magnetic disk.
When the host sends commands designating different target positions randomly, it is inefficient to execute the commands in the order in which the controller receives the commands, because the head has to repeatedly move back and forth along the head's stroke toward the different target positions, and then has to wait for the rotation of the magnetic disk until the head is above the current target positions. Theoretically, it would be ideal to consider all orders of executing the commands and execute them in accordance with a most efficient order (i.e., an optimal order). However, the significant number of computations required to determine the optimal order and the associated amount of time required for the computations generally prevent the consideration of all orders. This is especially true when the number of commands is very large, because the number of computations increases as the number of commands increases. For example, if the number of non-executed commands is N, the number of possible command orderings will be N!
Another scheme for determining the order of executing commands employs a “nearest neighbor” algorithm. According to this algorithm, a command that requires a least amount of time to start executing is selected as the next command to be executed. Although this algorithm may not lead to the most efficient order, the algorithm can save a large amount of computation and enable the storage device to make a good choice of the next command to be executed while executing a current command. For example, if the number of non-executed commands is N, the number of possible commands that can be the next command is N. However, even when the “nearest neighbor” algorithm is applied, the number of computations required to determine the next command may become too large for a large number of non-executed commands.